The invention relates to FIFO (first in, first out) devices which are widely used in data processing and digital signal processing, more particularly to provide buffer storage. The invention relates more particularly to FIFO devices which are asynchronous, i.e. which do not demand a predetermined time relationship between the input and the output, of the kind comprising a cascade stack of p identical data storage registers, and a control arrangement of p identical subassemblies each associated with one of the registers (p being an integer).
In a typical example, the FIFO comprises a stack of p registers all comprising the same number of bit positions, the logic control arrangement being formed by a mechanism with p bit positions each associated with a storage register.
The FIFO is so designed that a data word fed into the first register progresses spontaneously from register to register until it becomes stabilized in the last available register. Each reading "empties" the last register of the stack, and all information words stored go down by one step in the FIFO.
FIG. 1 shows a conventional embodiment of such a FIFO. Each of the registers 10.sub.1, . . . 10.sub.p is associated with a subassembly comprising a RS flip-flop 12.sub.1, . . . 12.sub.p, all FFs being in cascade. Each subassembly delivers a logic signal which acts on the associated register and indicates the empty or full condition thereof. The logic signal is produced as a function of the output signals of the preceding (or upstream) subassembly, the following (or downstream) subassembly, and the subassembly itself, the two end subassemblies of course requiring a slightly different arrangement.
Referring to FIG. 1, when the (i)th subassembly contains a binary 1, while the (i+1)th subassembly contains a 0, the subassembly (i+1) delivers, via an AND gate 14, a control signal for loading the register of rank (i+1), such signal being used to set the subassembly (i+1) at 1, and to reset the subassembly (i) to 0.
Therefore, the output logic signal of a subassembly such as 12.sub.1 acts on the following subassembly, for example, 12.sub.2, only after passing through the subassembly itself, as shown by the connections in heavy lines in FIG. 1, where the various inputs and outputs have the usual abbreviations:
SI : writing request (shift in) PA1 SO : reading request (shift out) PA1 DE : data input PA1 DS : data output PA1 IR : input validation (input ready) PA1 OR : reading validation (output ready).
Such a system therefore has a considerable response time.
FIG. 1 also shows in brackets the abbreviations conventionally used on components of French origin.
In a FIFO of the kind illustrated in FIG. 1 the data falls through the data registers at the rate of the set and reset of the RS FFs; if the FIFO, which may be considered as a queue, is almost empty, the fall through (the interval between the inputting of a data word into the first register and the availability of the word at the output) lasts for a considerable time, since the registers 10.sub.1 to 10.sub.p copy the item of information in response to the successive logic signals delivered by the corresponding subassemblies.
It is an object of the invention to supply a FIFO or queueing device of the kind specified which operates rapidly and almost independently of the degree to which the FIFO is filled and is however simple in construction.
According to the invention, there is provided particularly a FIFO device in which the data storage registers are of the type having a latched condition and a transparent condition. Each subassembly comprises switch means having a first input connected to receive a logic signal indicative of the condition of the subassembly, a second input connected to receive a logic signal indicative of the condition of the following subassembly and an output connected to the associated one of said data storage registers. The switch means is constructed to deliver on its output a signal indicative of the state of either the upstream or the downstream subassembly, in dependence on whether the subassembly comprising the switch means is free or not.
The individual registers embodied in the invention can be of various types available in the trade, for example they can be F100-150 registers (FAIRCHILD). In such a register, a data word applied at the input appears instantly at the output when the control input is at a first logic level. When such control input passes to a second logic level, the data applied at the input of the register immediately before the transition remains available at the output.
As a result of the use of such registers, the sequence of registers causes no slowing down of the fall through of the data along the cascade when the registers are clear and transparent.
Substitution of registers having a "transparent" state for conventional registers used for forming FIFOs in the prior art may at first glance appear as obvious. However, mere substitution does not provide an advantage, since the control bit of the control registers which accompanies the data word during its fall through in the cascade must also progress far enough to enable access to the data at the output. However, progression by "request-acknowledgment" in the RS FFs used in the prior art subassemblies is slow by nature, so that the substitution of one type of register for another is in itself no advantage and would normally be disregarded as being useless.
To get over the problem, the inventors completely set aside the prior art approaches as regards the make-up of the subassemblies. In the queueing device according to the invention, as defined hereinbefore, the control logic arrangement is such as to deliver exclusively, during the writing operation, logic state signals which fall through along with the data through the data storage registers until the data reaches the last empty register preceding a full register.
In a preferred embodiment each switch means is a 2-to-1 multiplexer. The output of the multiplexer directly controls the state of the associated storage register.
In general, each multiplexer will have an input connected to the output of the multiplexer of the preceding stage, an input connected to the output of the followng stage, and a control input connected to its own output, the associated register being transparent when it receives a logic "zero" from the multiplexer output, which reflects the state of the input connected to the preceding multiplexer when the control input receives a zero, and reflects the state of the input connected to the following multiplexer when the control input receives a 1.
To enable the sequence of multiplexers to operate correctly, as a rule the rise of the information bit from each multiplexer to the preceding one must be delayed. For this purpose, it is sufficient to apply the output of each multiplexer to the preceding one via a time delay element. The delay element will be such that the sum of the delay which it provides and the time for passing through the multiplexer is greater than the switching time of the multiplexer.
The FIFO may be provided with state-indicating outputs taken from the outputs of the switches of at least certain of the stages or sections. A logic filter cell can be located on each of the outputs for eliminating transients caused by the descent or ascent of the data along the stack.
The invention will be more clearly understood from the following description of an examplary embodiment thereof, with reference to the accompanying drawings.